package leetcode.editor.cn;
//实现 int sqrt(int x) 函数。 
//
// 计算并返回 x 的平方根，其中 x 是非负整数。 
//
// 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 
//
// 示例 1: 
//
// 输入: 4
//输出: 2
// 
//
// 示例 2: 
//
// 输入: 8
//输出: 2
//说明: 8 的平方根是 2.82842..., 
//     由于返回类型是整数，小数部分将被舍去。
// 
// Related Topics 数学 二分查找 
// 👍 508 👎 0

//Java：x 的平方根
class P69Sqrtx {
    public static void main(String[] args) {
        Solution solution = new P69Sqrtx().new Solution();
        // TO TEST
        int x = 10;
        double sqrt = (9 + 0) / 2;
        System.out.println(sqrt);
        // int sqrt = solution.mySqrt(x);
        // System.out.println("非负整数 x 的平方根是: " + sqrt);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int mySqrt(int x) {
            // 第一种方法,开始
            // 第一种方法,结束
            //if(x==0) return 0;
            // if (x == 1) return 1;
            // int low = 0;
            // int high = x;
            // while (low + 1 < high) {
            //     int mid = (high + low) / 2;
            //     if (x / mid < mid) high = mid;//这是个应该注意的点，
            //         //用乘法的话会溢出
            //     else low = mid;
            // }
            // return low;
            // 第二种方法,开始
            // int low = 0;
            // int high = x;
            // while (low <= high) {
            //     long sqrt= (high + low) / 2;
            //     if (sqrt * sqrt > x) {
            //         high = (int) sqrt - 1;
            //     }
            //     if (sqrt * sqrt < x) {
            //         low = (int) sqrt + 1;
            //     }
            //     if (sqrt * sqrt == x) {
            //         return (int) sqrt;
            //     }
            // }
            // return high;
            // 第二种方法,结束
            // 第三种方法,开始

            // 注意：针对特殊测试用例，例如 2147395599
            // 要把搜索的范围设置成长整型
            // 为了照顾到 0 把左边界设置为 0
            long left = 0;
            // # 为了照顾到 1 把右边界设置为 x // 2 + 1
            long right = x / 2 + 1;  //对于一个非负数n，它的平方根不会大于（n/2+1）
            long mid = 0;
            long square = 0;
            while (left < right) {              //在left与right中寻找
                // 注意：这里一定取右中位数，如果取左中位数，代码会进入死循环
                // long mid = left + (right - left + 1) / 2;
                mid = (left + right + 1) >>> 1;    //左移一位与直接除二相比有巨大的时间差
                square = mid * mid;
                if (square > x) {
                    right = mid - 1;     //如果大于了则上界减一
                } else {
                    left = mid;          //如果小于了则下界补上来
                }
            }
            // 因为一定存在，因此无需后处理
            return (int) left;
            // 第三种方法,结束
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}